今日題目

題目連結：572. Subtree of Another Tree
題目主題：Tree, Depth-First Search, String Mathcing, Binary Tree, Hash Function

講完幾個常見的演算法主題以後，這兩天會開始分享 Hash 相關的主題。

簡單說說 Hash Function

我認為 Hash 的核心概念是簡化一個複雜的資料，讓資料有更好的效能處理問題，這個簡化不管是將資料變成數字或是字串都是有可能的。

另外有兩個重點：

• Hash 過後得到的值是有可能遇到碰撞的問題，也就是說兩個不一樣的資料 Hash 過後卻得到相同的值，這樣就是所謂的碰撞，在設計 Hash Function 時需要特別小心。
• Hash 過後得到的值，在不知道 Hash Function 邏輯的狀況下，理論上是很難推回到原本資料的長相。

題目解說

建議可以看看LeetCode原本的題目說明，這邊是用我的方式說明題目，參考就好。

題目會給兩個 Binary Tree 分別為 root 及 subRoot，如果 subRoot 有出現在 root 之中並且結構及節點值都相同，回傳 True，不符合條件回傳 False。

約束：

• root 的節點總數範圍在[1, 2000].
• subRoot 的節點總數範圍在 [1, 1000].
• -10的4次方 <= root.val <= 10的4次方
• -10的4次方 <= subRoot.val <= 10的4次方

範例1

輸入: root = [3,4,5,1,2], subRoot = [4,1,2]
輸出: true
解說: 上圖是LeetCode提供的範例圖，很明顯可以看到 subRoot 有出現在 root 裏面且結構及節點值都相同。

範例2

輸入: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
輸出: false
解說: 上圖是LeetCode提供的範例圖，雖然看得到 [4, 1, 2] 有出現在 root 之中，但最終輸出為 false 的原因是 2 節點的結構並不相同，root 這邊多 2 出現了子節點。

建議到這邊先停下來，嘗試自己解解看，若沒有想法可再繼續走下去。

解題的想像

文字描述

1. 寫一個方法將樹轉成字串。
2. 將題目給的 root 及 subRoot 轉成字串。
3. 若 subRoot 的字串有出現在 root 的字串中，代表這顆 subRoot 的樹有出現在 root 中，回True，相反的沒出現就回 False。

圖解過程

範例:
root = [5, 4, 1, 7, 2]
subRoot = [4, 7, 2]

上圖是過程中，分別會先將 root 及 subRoot 這兩個複雜的樹簡化成一個字串，之後便可以直接用這兩個字串比對出subRoot 是否有出現在 root 中，以這個範例來說是有比對到 subRoot 轉成的字串是有出現在 root 字串之中的紅色底線部份，因此會回傳 True。

這個樹轉換成字串的過程，是運用了Preorder、Inorder、Postorder的方式組成的字串，每個數字至少會被經過三次，這樣可以確認到結構的長相。

上圖中，黑色數字是Preorder經過時紀錄的、紅色數字是Inorder經過時紀錄的、綠色數字就是Postorder經過的，這樣轉換出來的字串便可完整的去確認 root 中是否有出現跟 subRoot 結構及節點值都相同的樹。

若因為沒想法而走到這邊，建議看完想像以後再給自己一次機會試一次。

程式碼撰寫

class Solution:
    def convertString(self, root, rootStr = ''):
        if root == None: return rootStr
        
        rootStr += str(root.val)
        rootStr = self.convertString(root.left, rootStr)
        rootStr += str(root.val)
        rootStr = self.convertString(root.right, rootStr)
        rootStr += str(root.val)
        
        return rootStr
        
    
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        subRootStr = self.convertString(subRoot)
        rootStr = self.convertString(root)
        
        return subRootStr in rootStr

希望您今天能瞭解到...

1. Hash Function 的基本概念
2. 572. Subtree of Another Tree 的解題方法

若內容有什麼問題或建議歡迎一起交流：）
感謝您今天願意花時間看完這篇文章~~~~

Next：1. Two Sum